class Solution {
    public String addBinary(String a, String b) {
        //先转成二进制
        //parseInt()函数可解析一个字符串，并返回一个整数。
        //parseInt('123', 5) // 将'123'看作 5 进制数，返回十进制数 38 => 1*5^2 + 2*5^1 + 3*5^0 = 38
        //如果字符串超过 333333 位，不能转化为 Integer,如果字符串超过 656565 位，不能转化为 Long,如果字符串超过 500000001500000001500000001 位，不能转化为 BigInteger
        //BigInteger aMun = Integer.parseInt(a,2);
        //BigInteger bMun = Integer.parseInt(b,2);
        //BigInteger ab = aMun + bMun;
        //toBinaryString()返回long数据的二进制表示法,此方法的返回类型为String
        //return Integer.toBinaryString(ab);

        StringBuilder res = new StringBuilder(); // 返回结果
        int i = a.length() - 1; // 标记遍历到 a 的位置
        int j = b.length() - 1; // 标记遍历到 b 的位置
        int carry = 0; // 进位
        while (i >= 0 || j >= 0 || carry != 0) { // a 没遍历完，或 b 没遍历完，或进位不为 0
            int digitA = i >= 0 ? a.charAt(i) - '0' : 0; // 当前 a 的取值
            int digitB = j >= 0 ? b.charAt(j) - '0' : 0; // 当前 b 的取值
            int sum = digitA + digitB + carry; // 当前位置相加的结果
            carry = sum >= 2 ? 1 : 0; // 是否有进位
            sum = sum >= 2 ? sum - 2 : sum; // 去除进位后留下的数字
            res.append(sum); // 把去除进位后留下的数字拼接到结果中
            i --;  // 遍历到 a 的位置向左移动
            j --;  // 遍历到 b 的位置向左移动
        }
        return res.reverse().toString(); // 把结果反转并返回
    }
}